package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;

// 将单向链表按某值划分为左边小，中间相等，右边大的形式
// 难度：简单

/**
 * 标题：将单向链表按某值划分为左边小，中间相等，右边大的形式 | 时间限制：2秒 | 内存限制：262144K
 * 给定一个链表，再给定一个整数 pivot，请将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点， 右边部分都是大于 pivot 的节点。
 * 除此之外，对调整后的节点顺序没有更多要求。
 *
 * 输入描述:
 * 第一行两个整数 n 和 pivot，n 表示链表的长度。
 * 第二行 n 个整数表示链表的节点。
 *
 * 输出描述:
 * 请在给定的函数内返回链表的头指针。
 *
 * 示例1
 * 输入
 * 5 3   5是链表长度  3是pivot基准值  这个基准值可能在链表中，也可能不在链表中，这个不做要求
 * 9 0 4 5 1   链表
 *
 * 输出
 * 1 0 4 5 9   1 0都小于3，4 5 9都大于3。至于1 0内部和4 5 9内部，不做顺序的要求。
 * 或者
 * 0 1 9 4 5 都可以
 *
 *  5 3
 *  9 2 1 3 5
 *  输出结果  2 1 3 9 5
 *
 * 方案一：转为用数组放。然后呢，类似于数组的快排那样处理
 * 需要额外空间，另外，实现的内容多余要求的内容，因为，快排的话，数组的整体每个元素之间都是有序的
 * 思路（左神版）：
 * 1. 将链表存到数组中
 * 2. 利用快排的partion函数调整数组
 * 3. 将数组重新连成链表
 *
 * 方案二：要解决这个问题，我们可以使用三个链表分别存储小于 pivot 的节点，等于 pivot 的节点，大于 pivot 的节点，
 * 最后将它们连接在一起形成最终的链表。
 * 采取使用3个指针，把原链表依次划分成三个部分的链表，然后再把他们首位接续起来，
 * 这种做法不但空间复杂度为 O(1), 而且内部节点的顺序也是和原链表一样的。
 * 虽然思路简单，但在代码实现上也是有很多细节需要注意的，有时间的话希望大家动手打下码。
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Q16_PartitionLinkedList {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String line1 = sc.nextLine();
        int[] number1 = Utils.scannerAndTransIntoInt(line1);
        int n = number1[0];
        int pivot = number1[1];

        ListNode head = null, pre = null;

        String line2 = sc.nextLine();
        int[] number2 = Utils.scannerAndTransIntoInt(line2);
        for (int i = 0; i < n; i++) {
            int value = number2[i];
            ListNode currentNode = new ListNode(value);

            if (head == null) {
                head = currentNode;
                pre = head;
            } else {
                pre.next = currentNode;
                pre = pre.next;
            }
            // 最后一个节点额外后面还要加个null节点
            if (i == n - 1) {
                pre.next = null;
            }
        }

        ListNode result = partition(head, pivot);
        printList(result);
    }

    private static ListNode partition(ListNode node, int pivot) {

        // 三个单向链表的头节点的初始值
        // 这三个变量是用在循环中不断改变的，它不是累积的关系，它仅仅表示当前的关系，你可以认为它表示的是循环时的当前节点。
        // 当循环结束后，这三个变量其实表示的head1、head2、head3的三个链表的最后一个节点(不是指为null的那个最后节点)。
        ListNode less = new ListNode(-1);
        ListNode equal = new ListNode(-1);
        ListNode great = new ListNode(-1);

        // 三个单向链表的头节点的初始值。其实这个是哑结点，不是真正的头节点。真正的头节点到时候是xx.next这种。
        // 之所以这样做，是一种链表题中的常见做法，据说是可以简化逻辑。
        // 这三个后续变量后续就是表示三个链表的头节点。一直累积关系。用这三个节点可以分别代表它们对应完整的链表。
        ListNode head1 = less;
        ListNode head2 = equal;
        ListNode head3 = great;

        // node是原始链表的头节点。从原始链表的头结点一直往后循环，直到循环到null后停止。
        while (node != null) {

            // 以下就是在分别焊接三个子链表
            if (node.val < pivot) {
                less.next = new ListNode(node.val);
                less = less.next;
            } else if (node.val > pivot) {
                great.next = new ListNode(node.val);
                great = great.next;
            } else {
                equal.next = new ListNode(node.val);
                equal = equal.next;
            }

            // 这是在取原始列表的下一个节点
            node = node.next;
        }

        //head3.next才是真正的头节点。如果头节点不为空，代表原始链表里面存在大于pivot的元素
        // if内部的动作做的事情是，把head2链表中的最后一个节点(当然不是指那个null节点)equal，连接上head3链表的真正头节点head3.next
        if (head3.next != null) {
            equal.next = head3.next;
            // 把大于链表头部的哑节点断开
            // 把一个节点的下一个节点置空，意味着把这个节点和其他分开关系???
            // 实际试验了，即使注释掉这句，也不影响最终打印结果，那么就暂时注释掉不增加理解成本了。
            //head3.next = null;
        }

        //head2.next才是真正的头节点。如果头节点不为空，代表原始链表里面存在等于pivot的元素
        // 上面做完后，head2与head3已经连接。下面if括号内做的是，把head1链表的最后一个节点(不是指那个null节点)连接上head2的真正头结点
        if (head2.next != null) {
            less.next = head2.next;
            // 把等于链表头部的哑节点断开。暂时注释，不增加理解成本。
            //head2.next = null;
        }

        // 返回连接后的完整链表的真真头节点
        return head1.next;
    }

    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}